package formal.tree;

/**
 * 键值映射-前缀树
 * 全是大神的写法
 * @author DengYuan2
 * @create 2021-01-27 21:27
 */
public class MapSum {
    private class Node{
        Node[] child = new Node[26];
        int val;
    }

    private Node root = new Node();
    public MapSum(){

    }

    public void insert(String key,int val){
        insert(key,root,val);
    }

    public void insert(String key,Node node,int val){
        if (node==null){
            return;
        }
        if (key.length()==0){
            node.val=val;
            return;
        }
        int index = getIndex(key.charAt(0));
        if (node.child[index]==null){
            node.child[index]=new Node();
        }
        insert(key.substring(1),node.child[index],val);
    }

    /**
     * 我觉得用迭代的话可以这么写
     * @param key
     * @param val
     */
    public void insert2(String key,int val){
        if (key.length()==0){
            return;
        }
        Node cur = root;
        for (int i = 0; i < key.length(); i++) {
            int index = getIndex(key.charAt(i));
            if (cur.child[index]==null){
                cur.child[index]=new Node();
            }
            cur=cur.child[index];
            if (i==key.length()-1){
                cur.val=val;
            }
        }
    }

    public int sum(String prefix){
        int sum = sum(prefix,root);
        return sum;
    }

    public int sum(String prefix,Node node){
        if (node==null){
            return 0;
        }
        if (prefix.length()!=0){
            int index = getIndex(prefix.charAt(0));
            return sum(prefix.substring(1),node.child[index]);
        }
        //此时node即为前缀所在的根节点啦
        int sum = node.val;
        if (node.child!=null){
            for (int i = 0; i < 26; i++) {
                sum+=sum("",node.child[i]);
            }
        }
        return sum;
    }


    public int getIndex(char c){
        return c-'a';
    }

}
